package leetcode_400;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 *@author 周杨
 *PatchingArray_330_ 给定一个候选数组 和一个n 问最少加入几个数字能使所有的候选数能表示1-n的所有数 
 *describe:用贪心算法 AC 100%
 *2018年7月5日 下午4:18:03
 */
public class PatchingArray_330_ {
	Set<Integer> help=new TreeSet<Integer>();
	public static void main(String[] args) {
		PatchingArray_330_ test=new PatchingArray_330_();
		//System.out.println(test.minPatches(new int[] {1,5,10},20));
		System.out.println(test.minPatches(new int[] {},7));

	}
	
	
	    /**
	     * describe:cur表示当前能表示的范围为[1..cur],扫描nums[ ]，贪心原则如下：

     		若nums[i]<=2*cur + 1,把nums[i]添加进来，表示范围更新[1..cur+nums[i]];

     		若nums[i]>2*cur + 1,添加新的元素cur+1,表示范围更新[1..2*cur+1].
	     * 2018年7月5日 下午4:17:50
	     */
	    public int minPatches2(int[] nums, int n) {
	        long miss = 1;
	        int add = 0;
	        int i = 0;
	        while (miss <= n) {
	            if (i < nums.length && nums[i] <= miss){
	                miss += nums[i++];
	            } else {
	                miss += miss;
	                add += 1;
	            }
	        }
	        return add;
	    }


	
		/**
		 * describe:完美方法 贪心算法
		 * 2018年7月5日 下午2:04:43
		 */
		public int minPatches1(int[] nums, int n) {
	        long max = 0;
			int cnt = 0;
			for (int i = 0; max < n;) {
				if (i >= nums.length || max < nums[i] - 1) {
					max += max + 1;
					cnt++;
				} else {
					max += nums[i];
					i++;
				}
			}
			return cnt;
	    }
	
	
	/**
	 * describe:用TreeSet每次选取miss中最小值 然后与Help里匹配  超时
	 * 2018年7月5日 下午2:03:07
	 */
	public int minPatches(int[] nums, int n) {
        List<Integer> miss=new ArrayList<Integer>();
        for(int i=1;i<=n;++i)
        	miss.add(i);
        for(int i=0;i<nums.length;++i)
        	help(nums,i,0);
        int res=0;
        for(Integer i:help) {
        	miss.remove(i);
        }
        while(!miss.isEmpty()) {
        	Integer min=miss.get(0);
        	++res;
        	List<Integer> temp=new ArrayList<Integer>();
        	for(Integer i:help) {
        		Integer now=new Integer(i+min);
        		temp.add(now);
        		miss.remove(now);
        	}
        	help.addAll(temp);
        	help.add(min);
        	miss.remove(min);
        }
        return res;
    }
	
	public	void help(int []nums,int index,int sum){
		if(index==nums.length)
			return ;
		int res=sum+nums[index];
		this.help.add(res);
		for(int i=index+1;i<nums.length;++i) {
			help(nums,i,res);
		}
	} 
	
	
	
}	
